package J1_22;

import java.util.Stack;

public class test {

    /*给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    每个右括号都有一个对应的相同类型的左括号。*/
    public static boolean isValid(String s) {
        if (s == "") {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        for (char x: s.toCharArray()) {
            if (x == '(' || x == '{' || x == '[') {
                stack.push(x);
            }else {
                switch(x) {
                    case ')':
                        if (!stack.empty() && stack.peek() == '(') {
                            stack.pop();
                            break;
                        } else {
                            return false;
                        }
                    case '}':
                        if (!stack.empty() && stack.peek() == '{') {
                            stack.pop();
                            break;
                        } else {
                            return false;
                        }
                    case ']':
                        if (!stack.empty() && stack.peek() == '[') {
                            stack.pop();
                            break;
                        } else {
                            return false;
                        }
                }
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }

    /*给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    请你计算该表达式。返回一个表示表达式值的整数。*/
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String x: tokens
             ) {
            if (!x.equals("+") && !x.equals("-") && !x.equals("*") && !x.equals("/")) {
                stack.push(Integer.parseInt(x));
            } else {
                int a2 = stack.pop();
                int a1 = stack.pop();
                switch(x) {
                    case "+":
                        stack.push(a1 + a2);
                        break;
                    case "-":
                        stack.push(a1 - a2);
                        break;
                    case "*":
                        stack.push(a1 * a2);
                        break;
                    case "/":
                        stack.push(a1 / a2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    //输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
    // 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int n = popV.length;
        int j = 0;
        for (int i = 0; i < n; i++) {
            stack.push(pushV[i]);
            while (j<n && !stack.empty() && popV[j] == stack.peek()) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
    public static void main(String[] args) {
        String s =  "()";
        System.out.println(isValid(s));
        System.out.println(isValid(s));

    }

}
